/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package com.factory.server.algorithms;

import com.factory.server.bo.Prime;
import java.util.ArrayList;
import java.util.List;

/**
 *Implementation of Erathostenes sieve
 * @author
 * http://www.vogella.com/articles/JavaAlgorithmsPrimeNumbers/article.html
 */
public class Eratosthenes {

    public static List<Prime> execute(int lowerBound, int upperBound, int maximalPrime) {
        List<Prime> primes = new ArrayList<Prime>();
        int upperBoundSquareRoot = (int) Math.sqrt(upperBound);
//        boolean[] isComposite = new boolean[(int) upperBound + 1];
        boolean[] isComposite = new boolean[(int) upperBound + 1];

        for (int m = 2 /*int m = lowerBound*/; m <= upperBoundSquareRoot; m++) {

            if (!isComposite[m]) {

                if (m >= lowerBound) {
                    if (m > maximalPrime) { // tolko uz mam vypocitane
                        primes.add(new Prime((int)m));
                    }
                }
                for (int k = m; k <= upperBound; k += m) {
                    isComposite[k] = true;
                }
            }
        }

        for (int m = (int) upperBoundSquareRoot; m <= upperBound; m++) {
            if (!isComposite[m]) {
                if (m > lowerBound) {
                    if (m > maximalPrime) { // tolko uz mam vypocitane
                        primes.add(new Prime((int)m));
                    }
                }
            }
        }
        return primes;
    }
}
